# 20230414_1.破冰船问题
# 一艘破冰船停在冰面上，冰面被分成一块块的区域，船的初始区域为破冰区域，其余区域为冰面区域。
# 船可以上下左右移动，如果船驶入一个冰面区域，则为破冰一次。冰面在破冰船离开limit时间后会重亲冻，
# 破冰船驶入破冰区域后，破冰区域的结冻时间会重新计时。方法:
# ·输入参数1:String参数(长度小于等于1000)，字符串的每个字符表示破冰船的动作，如
# “URLDRRLD”。共有4种动作【U、D、L、R分别表示破冰船的上下左右移动】。
# 输入参数2:int参数，表示冰面重新结冻时间·输出:破冰船在行驶过程中破冰次数
#
# 解法:
# 典型的走迷宫，上下左右。由于没有传入坐标，所以根本不用数组。
# 将每通过一次封装为一个Step类，记录当前坐标，通过的时间。然后装入集合中，我使
# 用的是ArrrayList。
# 计算下一次行走的坐标的时候，就在当前的的坐标上加减即可，
# 坐标可能会减小到负数，这个完全不影响，只是个x，y而已。
# 在list中找到上次通过的记录，然后对比当前时间和上次时间是否超过limit，判断是否破冰。
# 测试用例1:
# 没有保存数据
# 测试用例2:
# 输入:RDDUURDLLURU输出:9

def GetIceBreak(route: str, limit:int) -> int:
  Dir = {'U':(0,1), 'D':(0-1), 'L':(-1,0), 'R':(1,0)}
  ans = time = x = y = 0
  trace = {(0,0):0}
  for d in route:
    time+=1
    x += Dir[d][0]
    y += Dir[d][1]
    if (x, y) in trace:
      if trace[(x,y)] + limit <= time:
        ans += 1
    else:
      ans += 1
    trace[(x,y)] = time
  return ans
